/**
 * The neighbour-finding part of BellKor's k-Nearest Neighbours algorithm.
 * Bell, Koren (2007). Improved Neighbourhood-based Collaborative Filtering
 * (kdd-2007-cf-workshop on their website)
 *
 * Usage:
 * ... query_file similarity_file k <training_set
 *
 * query_file: sorted by user, in format for query_by_user_cursor_t 
 * similarity_file: NUM_MOVIES by NUM_MOVIES symmetric matrix in binary
 *                  (float) format)
 * k: number of neighbours (positive)
 * training_set: sorted by user, in format for ratings_by_user_block_cursor_t
 * Outputs the neighbours on stdout in the format.
 * user_id movie_id num_neighbours neighbour_id rating neighbour_id rating...
 * user_id movie_id num_neighbours neighbour_id rating neighbour_id rating...
 * ...
 */
#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include "u1.h"
#include "symmetric_matrix.h"
#include "io.h"
#include "toplist.h"

using namespace std;

struct F_similarity_greater
{
  const symmetric_matrix<float> &S;
  int id;
  F_similarity_greater(const symmetric_matrix<float> &S, int id) : S(S), id(id)
  { }
  bool operator()(const id_rating_t<float> &a,
      const id_rating_t<float> &b) const
  {
    return S(id-1, a.id-1) > S(id-1, b.id-1);
  }
};

int main(int argc, char **argv) {
  if (argc != 4) {
    TRACE<<"see comments for usage"<<endl;
    exit(EXIT_FAILURE);
  }

  string query_file = argv[1];
  string similarity_file = argv[2];
  int k_int = atoi(argv[3]); 

  if (k_int < 1) {
    TRACE<<"invalid k = "<<k_int<<endl;
    exit(EXIT_FAILURE);
  }
  size_t k = (size_t)k_int;

  // Read movie-movie similarity matrix from binary file into memory.
  TRACE<<"loading similarities from "<<similarity_file<<endl;
  symmetric_matrix<float> S(NUM_MOVIES);
  ifstream S_is(similarity_file.c_str());
  S.read_binary(S_is);
  S_is.close();

  // Read query set from file and (much larger) training set from stdin.
  TRACE<<"reading queries from "<<query_file<<endl;
  ifstream query_is(query_file.c_str());
  query_by_user_cursor_t qs(query_is);
  ratings_by_user_block_cursor_t<float> ts(cin);

  // Don't lose too many digits when printing.
  cout.precision(8);

  for(; qs; ++qs) {
    // Find movies that have been rated by the query user (neighbour movies).
    // All users in query set must appear somewhere in training set.
    while (ts && ts.user_id() != qs.user_id()) {
      assert(ts.user_id() < qs.user_id());
      ++ts;
    }
    assert(ts);

    // Keep only the k most similar neighbours.
    toplist<id_rating_t<float>, F_similarity_greater> neighbours(k,
      F_similarity_greater(S, qs.movie_id()));
    for(ratings_by_user_block_cursor_t<float>::const_iterator
        it = ts.begin(); it != ts.end(); ++it)
    {
      neighbours.insert(*it);
    }

    // Write out neighbourhood.
    cout<<qs.movie_id()<<" "<<qs.user_id()<<" "<<neighbours.size()<<" ";
    copy(neighbours.begin(), neighbours.end(),
        ostream_iterator<id_rating_t<float> >(cout, " "));
    cout<<'\n';
  }

  query_is.close();

  TRACE<<"done"<<endl;

  return 0;
}

/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

